template<class T>
struct Fenwick {
  Fenwick(int _n) : n_(_n), tr_(_n + 1) {}

  void add(int p, const T v) {
    for (int i = p; i <= n_; i += (i & -i)) {
      tr_[i] = tr_[i] + v;
    }
  }

  T query(int p) {
    T res = T();
    for (int i = p; i > 0; i -= (i & -i)) {
      res = res + tr_[i];
    }
    return res;
  }

  T query(const int l, const int r) {
    if (l <= 0 || l > r || r > n_) {
      return T();
    }
    return query(r) - query(l - 1);
  }

  // 找到第一个大于k的地方
  T kth(T k) {
    int pos = 0;
      for(int j = 31 - __builtin_clz(n_);j >= 0;j --) {
        if(pos + (1 << j) <= n_ && k >= tr_[pos + (1 << j)]) {
          pos += 1 << j;
          k = k - tr_[pos];
        }
      }
      return pos + 1;
  }

  int n_;
  vector<T> tr_;
};